package oct2013.linkednode;

public class UniqueBinarySearchTrees {
	public int numTrees(int n) {
		return (int) (combination(2 * n, n) / (n + 1));
	}

	long combination(int n, int k) {
		long res = 1;
		for (int i = 1; i <= k; ++i) {
			res *= (n - i + 1);
			res /= i;
		}
		return res;
	}

	// recursive version
	static int[] dp;
	static {
		dp = new int[100];
		dp[0] = 1;
		dp[1] = 1;
	}

	public int numTreesRecursive(int n) {
		if (dp[n] != 0)
			return dp[n];
		for (int i = 0; i < n; ++i) {
			dp[n] += numTreesRecursive(i) * numTreesRecursive(n - i - 1);
		}
		return dp[n];
	}

}
